#index range from 0...n-1
def left(i):
    return 2*i+1
def right(i):
    return 2*i+2
def max_heapify_recursive(A,i): #小的元素下沉
    heapsize=len(A)
    L=left(i)
    R=right(i)
    largest=i
    if L<heapsize and A[L]>A[i]:
        largest=L
    if R<heapsize and A[R]>A[largest]:
        largest=R
    if largest!=i:
        A[i],A[largest]=A[largest],A[i]
        max_heapify(A,largest)
def max_heapify(A,i): #小的元素下沉
    heapsize=len(A)
    finished=False
    while i<=heapsize//2 and finished is False:
        L=left(i)
        R=right(i)
        largest=i
        if L<heapsize and A[L]>A[i]:
            largest=L
        if R<heapsize and A[R]>A[largest]:
            largest=R
        if largest!=i:
            A[i],A[largest]=A[largest],A[i]
            i=largest
        else: #largest==i
            finished=True

if __name__=='__main__':
    A=[16,4,10,14,7,9,3,2,8,1] #CLRS pp.131
    print 'A:', A
    max_heapify(A,1)
    print 'A:', A
